package eda.hashTable;

import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.LinkedList;

import eda.util.ADTNoSuchElement;
import eda.util.ADTOverflowException;
import eda.util.ADTUnderflowException;
import eda.util.Constants;

/**
 * Estrutura representa uma tabela hash que funciona tanto com enderecamento
 * fechado (com chaining) quanto como enderecamento aberto. No caso de enderecamento
 * aberto ela pode funcionar com linear probe, probe quadratico ou double hashing. 
 * A forma de como a tabela vai trabalhar depende das informacoes fornecidas pelo 
 * usuario (se enderecamento aberto ou fechado, e se enderecamento aberto que tipo de 
 * probe). 
 * A estrutura deve ter um tamanho inicial, um tamanho maximo que pode 
 * crescer e um FATOR de crescimento. Quando instanciada a estrutura tem um tamanho 
 * inicial. Quando ela vai crescendo e atinge 75% de sua capacidade, ela aumenta de 
 * tamanho (e deve fazer um rehash nos elementos) de acordo com o fator de crescimento desde que nao atinja ou ultrapasse o tamanho  
 * maximo. A partir dai a estrutura nao pode mais crescer e pode ficar cheia. Use as constantes 
 * definidas em eda.util.Constantes para inicializar os valores internos de sua 
 * estrutura. Faca protected qualquer outro metodo auxiliar.
 */
public class HashTableChaining<K, V> implements HashTable<K, V> {
	
	private LinkedList<HashTableElement<K, V>>[] table;
	private int numberOfElements;
	private final double MULTIPLICATION_CONSTANT = (double)(Math.sqrt(5) - 1)/2;
	
	@SuppressWarnings("unchecked")
	protected HashTableChaining(){
		this.numberOfElements = 0;
		this.table = (LinkedList<HashTableElement<K, V>>[]) Array.newInstance(LinkedList.class, Constants.INITIAL_SIZE_OF_STRUCTURE);
		for ( int i=0; i<table.length; i++ ){
			table[i] = new LinkedList<HashTableElement<K,V>>();
		}
	}
	
	@Override
	public boolean isEmpty() {
		return this.numberOfElements == 0;
	}

	@Override
	public boolean full() {
		boolean hasNoEmptyList = true;
		for ( LinkedList<HashTableElement<K, V>> list : table ){
			if ( list.isEmpty() ){
				hasNoEmptyList = false;
				break;
			}
		}
		return hasNoEmptyList;
	}

	@Override
	public int size() {
		return this.numberOfElements;
	}

	@Override
	public void insert(K key, V value) throws ADTOverflowException {
		
		if (full()) {
			throw new ADTOverflowException();
		}
		
		int index = hashPosition(key);
		this.table[index].add(new HashTableElement<K, V>(key, value));
		
		this.numberOfElements++;
		
		if (this.numberOfElements >= this.table.length*0.75 && table.length < Constants.MAX_SIZE_OF_STRUCTURE) {
			rehash(this.table);
		}
	}
	
	@Override
	public void remove(K key) throws ADTUnderflowException, ADTNoSuchElement {
		
		if (numberOfElements == 0) {
			throw new ADTUnderflowException();
		}
		
		int index = hashPosition(key);
		LinkedList<HashTableElement<K, V>> linkedList = table[index];
		
		Iterator<HashTableElement<K,V>> iterator = linkedList.iterator();

		HashTableElement<K, V> toBeRemoved = null;
		
		while ( iterator.hasNext() ){
			HashTableElement<K, V> element = iterator.next();
			if ( element.getKey().equals(key) ){
				toBeRemoved = element;
				numberOfElements--;
			}
		}

		if (toBeRemoved == null) {
			throw new ADTNoSuchElement();
		}
		linkedList.remove(toBeRemoved);
	}

	@Override
	public V search(K key){
		int index = hashPosition(key);
		LinkedList<HashTableElement<K, V>> linkedList = table[index];
		HashTableElement<K, V> toBeReturned = null;
		
		Iterator<HashTableElement<K,V>> iterator = linkedList.iterator();
		while ( iterator.hasNext() ){
			HashTableElement<K, V> element = iterator.next();
			if ( element.getKey().equals(key) ){
				toBeReturned = element;
			}
		}
		
		if (toBeReturned == null) {
			return null;
		}
		
		return toBeReturned.getValue();
	}

	@Override
	public boolean containsKey(K key){
		return search(key) != null;
	}
	
	private int hashPosition(K key) {
		int hashPosition = 0;
		int keyHashCode = key.hashCode();
		
		hashPosition = hashingFunction(keyHashCode);

		if ( hashPosition < 0 ){
			hashPosition += table.length;
		}
		
		return hashPosition;
	}

	private int hashingFunction(int keyHashCode) {
		return (int)Math.floor(this.table.length*((keyHashCode*MULTIPLICATION_CONSTANT) % 1));
	}
	
	@SuppressWarnings("unchecked")
	private void rehash (LinkedList<HashTableElement<K, V>>[] oldTable) throws ADTOverflowException{
		
		if ( Constants.INCREASING_FACTOR+oldTable.length < Constants.MAX_SIZE_OF_STRUCTURE ){
			this.table = (LinkedList<HashTableElement<K, V>>[]) Array.newInstance(LinkedList.class, Constants.INCREASING_FACTOR+oldTable.length);
		}
		else{
			this.table = (LinkedList<HashTableElement<K, V>>[]) Array.newInstance(LinkedList.class, Constants.MAX_SIZE_OF_STRUCTURE);			
		}
		
		for ( int i=0; i<table.length; i++ ){
			table[i] = new LinkedList<HashTableElement<K,V>>();
		}
		this.numberOfElements = 0;
		
		for (int i = 0; i < oldTable.length; i++) {
			if (! oldTable[i].isEmpty() ) {
				for (int j = 0; j < oldTable[i].size(); j++) {
					HashTableElement<K, V> actualTableElement = oldTable[i].get(j);
					this.insert(actualTableElement.getKey(), actualTableElement.getValue());
				}
			}
		}
	}

	public String toString(){
		String toReturn = "[ ";
		
		for (int i = 0; i < this.table.length; i++) {
			if (i != this.table.length - 1) {
				toReturn += i + " = " + table[i].toString() + ", ";
			}
			else {
				toReturn += i + " = " + table[i].toString();
			}
		}
		toReturn += " ]";
		
		return toReturn;
	}
}